/*
+---------------------------------------------------------------------+
| iThinkphp     | [ WE CAN DO IT JUST THINK ]                         |
+---------------------------------------------------------------------+
| Official site | http://www.ithinkphp.org/                           |
+---------------------------------------------------------------------+
| Author        | hello wf585858@yeah.net                             |
+---------------------------------------------------------------------+
| Repository    | https://gitee.com/wf5858585858/iThinkphp            |
+---------------------------------------------------------------------+
| Licensed      | http://www.apache.org/licenses/LICENSE-2.0 )        |
+---------------------------------------------------------------------+
*/

// Released under MIT license
// Copyright (c) 2009-2010 Dominic Baggott
// Copyright (c) 2009-2010 Ash Berlin
// Copyright (c) 2011 Christoph Dorn <christoph@christophdorn.com> (http://www.christophdorn.com)

(function (expose) {

	/**
	 *  class Markdown
	 *
	 *  Markdown processing in Javascript done right. We have very particular views
	 *  on what constitutes 'right' which include:
	 *
	 *  - produces well-formed HTML (this means that em and strong nesting is
	 *    important)
	 *
	 *  - has an intermediate representation to allow processing of parsed data (We
	 *    in fact have two, both as [JsonML]: a markdown tree and an HTML tree).
	 *
	 *  - is easily extensible to add new dialects without having to rewrite the
	 *    entire parsing mechanics
	 *
	 *  - has a good test suite
	 *
	 *  This implementation fulfills all of these (except that the test suite could
	 *  do with expanding to automatically run all the fixtures from other Markdown
	 *  implementations.)
	 *
	 *  ##### Intermediate Representation
	 *
	 *  *TODO* Talk about this :) Its JsonML, but document the node names we use.
	 *
	 *  [JsonML]: http://jsonml.org/ "JSON Markup Language"
	 **/
	var Markdown = expose.Markdown = function Markdown(dialect) {
		switch (typeof dialect)
		{
			case "undefined":
				this.dialect = Markdown.dialects.Gruber;
				break;
			case "object":
				this.dialect = dialect;
				break;
			default:
				if (dialect in Markdown.dialects)
				{
					this.dialect = Markdown.dialects[dialect];
				}
				else
				{
					throw new Error("Unknown Markdown dialect '" + String(dialect) + "'");
				}
				break;
		}
		this.em_state = [];
		this.strong_state = [];
		this.debug_indent = "";
	};

	/**
	 *  parse( markdown, [dialect] ) -> JsonML
	 *  - markdown (String): markdown string to parse
	 *  - dialect (String | Dialect): the dialect to use, defaults to gruber
	 *
	 *  Parse `markdown` and return a markdown document as a Markdown.JsonML tree.
	 **/
	expose.parse = function (source, dialect) {
		// dialect will default if undefined
		var md = new Markdown(dialect);
		return md.toTree(source);
	};

	/**
	 *  toHTML( markdown, [dialect]  ) -> String
	 *  toHTML( md_tree ) -> String
	 *  - markdown (String): markdown string to parse
	 *  - md_tree (Markdown.JsonML): parsed markdown tree
	 *
	 *  Take markdown (either as a string or as a JsonML tree) and run it through
	 *  [[toHTMLTree]] then turn it into a well-formated HTML fragment.
	 **/
	expose.toHTML = function toHTML(source, dialect, options) {
		var input = expose.toHTMLTree(source, dialect, options);

		return expose.renderJsonML(input);
	};

	/**
	 *  toHTMLTree( markdown, [dialect] ) -> JsonML
	 *  toHTMLTree( md_tree ) -> JsonML
	 *  - markdown (String): markdown string to parse
	 *  - dialect (String | Dialect): the dialect to use, defaults to gruber
	 *  - md_tree (Markdown.JsonML): parsed markdown tree
	 *
	 *  Turn markdown into HTML, represented as a JsonML tree. If a string is given
	 *  to this function, it is first parsed into a markdown tree by calling
	 *  [[parse]].
	 **/
	expose.toHTMLTree = function toHTMLTree(input, dialect, options) {
		// convert string input to an MD tree
		if (typeof input === "string") input = this.parse(input, dialect);

		// Now convert the MD tree to an HTML tree

		// remove references from the tree
		var attrs = extract_attr(input),
			refs = {};

		if (attrs && attrs.references)
		{
			refs = attrs.references;
		}

		var html = convert_tree_to_html(input, refs, options);
		merge_text_nodes(html);
		return html;
	};

// For Spidermonkey based engines
	function mk_block_toSource()
	{
		return "Markdown.mk_block( " +
			uneval(this.toString()) +
			", " +
			uneval(this.trailing) +
			", " +
			uneval(this.lineNumber) +
			" )";
	}

// node
	function mk_block_inspect()
	{
		var util = require('util');
		return "Markdown.mk_block( " +
			util.inspect(this.toString()) +
			", " +
			util.inspect(this.trailing) +
			", " +
			util.inspect(this.lineNumber) +
			" )";

	}

	var mk_block = Markdown.mk_block = function (block, trail, line) {
		// Be helpful for default case in tests.
		if (arguments.length == 1) trail = "\n\n";

		var s = new String(block);
		s.trailing = trail;
		// To body it clear its not just a string
		s.inspect = mk_block_inspect;
		s.toSource = mk_block_toSource;

		if (line != undefined)
			s.lineNumber = line;

		return s;
	};

	function count_lines(str)
	{
		var n = 0, i = -1;
		while ((i = str.indexOf('\n', i + 1)) !== -1) n++;
		return n;
	}

// Internal - split source into rough blocks
	Markdown.prototype.split_blocks = function splitBlocks(input, startLine) {
		// [\s\S] matches _anything_ (newline or space)
		var re = /([\s\S]+?)($|\n(?:\s*\n|$)+)/g,
			blocks = [],
			m;

		var line_no = 1;

		if ((m = /^(\s*\n)/.exec(input)) != null)
		{
			// skip (but count) leading blank lines
			line_no += count_lines(m[0]);
			re.lastIndex = m[0].length;
		}

		while ((m = re.exec(input)) !== null)
		{
			blocks.push(mk_block(m[1], m[2], line_no));
			line_no += count_lines(m[0]);
		}

		return blocks;
	};

	/**
	 *  Markdown#processBlock( block, next ) -> undefined | [ JsonML, ... ]
	 *  - block (String): the block to process
	 *  - next (Array): the following blocks
	 *
	 * Process `block` and return an array of JsonML nodes representing `block`.
	 *
	 * It does this by asking each block level function in the dialect to process
	 * the block until one can. Succesful handling is indicated by returning an
	 * array (with zero or more JsonML nodes), failure by a false value.
	 *
	 * Blocks handlers are responsible for calling [[Markdown#processInline]]
	 * themselves as appropriate.
	 *
	 * If the blocks were split incorrectly or adjacent blocks need collapsing you
	 * can adjust `next` in place using shift/splice etc.
	 *
	 * If any of this default behaviour is not right for the dialect, you can
	 * define a `__call__` method on the dialect that will get invoked to handle
	 * the block processing.
	 */
	Markdown.prototype.processBlock = function processBlock(block, next) {
		var cbs = this.dialect.block,
			ord = cbs.__order__;

		if ("__call__" in cbs)
		{
			return cbs.__call__.call(this, block, next);
		}

		for (var i = 0; i < ord.length; i++)
		{
			//D:this.debug( "Testing", ord[i] );
			var res = cbs[ord[i]].call(this, block, next);
			if (res)
			{
				//D:this.debug("  matched");
				if (!isArray(res) || (res.length > 0 && !(isArray(res[0]))))
					this.debug(ord[i], "didn't return a proper array");
				//D:this.debug( "" );
				return res;
			}
		}

		// Uhoh! no match! Should we throw an error?
		return [];
	};

	Markdown.prototype.processInline = function processInline(block) {
		return this.dialect.inline.__call__.call(this, String(block));
	};

	/**
	 *  Markdown#toTree( source ) -> JsonML
	 *  - source (String): markdown source to parse
	 *
	 *  Parse `source` into a JsonML tree representing the markdown document.
	 **/
// custom_tree means set this.tree to `custom_tree` and restore old value on return
	Markdown.prototype.toTree = function toTree(source, custom_root) {
		var blocks = source instanceof Array ? source : this.split_blocks(source);

		// Make tree a member variable so its easier to mess with in extensions
		var old_tree = this.tree;
		try
		{
			this.tree = custom_root || this.tree || ["markdown"];

			blocks:
				while (blocks.length)
				{
					var b = this.processBlock(blocks.shift(), blocks);

					// Reference blocks and the like won't return any content
					if (!b.length) continue blocks;

					this.tree.push.apply(this.tree, b);
				}
			return this.tree;
		}
		finally
		{
			if (custom_root)
			{
				this.tree = old_tree;
			}
		}
	};

// Noop by default
	Markdown.prototype.debug = function () {
		var args = Array.prototype.slice.call(arguments);
		args.unshift(this.debug_indent);
		if (typeof print !== "undefined")
			print.apply(print, args);
		if (typeof console !== "undefined" && typeof console.log !== "undefined")
			console.log.apply(null, args);
	}

	Markdown.prototype.loop_re_over_block = function (re, block, cb) {
		// Dont use /g regexps with this
		var m,
			b = block.valueOf();

		while (b.length && (m = re.exec(b)) != null)
		{
			b = b.substr(m[0].length);
			cb.call(this, m);
		}
		return b;
	};

	/**
	 * Markdown.dialects
	 *
	 * Namespace of built-in dialects.
	 **/
	Markdown.dialects = {};

	/**
	 * Markdown.dialects.Gruber
	 *
	 * The default dialect that follows the rules set out by John Gruber's
	 * markdown.pl as closely as possible. Well actually we follow the behaviour of
	 * that script which in some places is not exactly what the syntax web page
	 * says.
	 **/
	Markdown.dialects.Gruber = {
		block: {
			atxHeader: function atxHeader(block, next) {
				var m = block.match(/^(#{1,6})\s*(.*?)\s*#*\s*(?:\n|$)/);

				if (!m) return undefined;

				var header = ["header", {level: m[1].length}];
				Array.prototype.push.apply(header, this.processInline(m[2]));

				if (m[0].length < block.length)
					next.unshift(mk_block(block.substr(m[0].length), block.trailing, block.lineNumber + 2));

				return [header];
			},

			setextHeader: function setextHeader(block, next) {
				var m = block.match(/^(.*)\n([-=])\2\2+(?:\n|$)/);

				if (!m) return undefined;

				var level = (m[2] === "=") ? 1 : 2;
				var header = ["header", {level: level}, m[1]];

				if (m[0].length < block.length)
					next.unshift(mk_block(block.substr(m[0].length), block.trailing, block.lineNumber + 2));

				return [header];
			},

			code: function code(block, next) {
				// |    Foo
				// |bar
				// should be a code block followed by a paragraph. Fun
				//
				// There might also be adjacent code block to merge.

				var ret = [],
					re = /^(?: {0,3}\t| {4})(.*)\n?/,
					lines;

				// 4 spaces + content
				if (!block.match(re)) return undefined;

				block_search:
					do
					{
						// Now pull out the rest of the lines
						var b = this.loop_re_over_block(
							re, block.valueOf(), function (m) { ret.push(m[1]); });

						if (b.length)
						{
							// Case alluded to in first comment. push it back on as a new block
							next.unshift(mk_block(b, block.trailing));
							break block_search;
						}
						else if (next.length)
						{
							// Check the next block - it might be code too
							if (!next[0].match(re)) break block_search;

							// Pull how how many blanks lines follow - minus two to account for .join
							ret.push(block.trailing.replace(/[^\n]/g, '').substring(2));

							block = next.shift();
						}
						else
						{
							break block_search;
						}
					} while (true);

				return [["code_block", ret.join("\n")]];
			},

			horizRule: function horizRule(block, next) {
				// this needs to find any hr in the block to handle abutting blocks
				var m = block.match(/^(?:([\s\S]*?)\n)?[ \t]*([-_*])(?:[ \t]*\2){2,}[ \t]*(?:\n([\s\S]*))?$/);

				if (!m)
				{
					return undefined;
				}

				var jsonml = [["hr"]];

				// if there's a leading abutting block, process it
				if (m[1])
				{
					jsonml.unshift.apply(jsonml, this.processBlock(m[1], []));
				}

				// if there's a trailing abutting block, stick it into next
				if (m[3])
				{
					next.unshift(mk_block(m[3]));
				}

				return jsonml;
			},

			// There are two types of lists. Tight and loose. Tight lists have no whitespace
			// between the items (and result in text just in the <li>) and loose lists,
			// which have an empty line between list items, resulting in (one or more)
			// paragraphs inside the <li>.
			//
			// There are all sorts weird edge cases about the original markdown.pl's
			// handling of lists:
			//
			// * Nested lists are supposed to be indented by four chars per level. But
			//   if they aren't, you can get a nested list by indenting by less than
			//   four so long as the indent doesn't match an indent of an existing list
			//   item in the 'nest stack'.
			//
			// * The type of the list (bullet or number) is controlled just by the
			//    first item at the indent. Subsequent changes are ignored unless they
			//    are for nested lists
			//
			lists: (function () {
				// Use a closure to hide a few variables.
				var any_list = "[*+-]|\\d+\\.",
					bullet_list = /[*+-]/,
					number_list = /\d+\./,
					// Capture leading indent as it matters for determining nested lists.
					is_list_re = new RegExp("^( {0,3})(" + any_list + ")[ \t]+"),
					indent_re = "(?: {0,3}\\t| {4})";

				// TODO: Cache this regexp for certain depths.
				// Create a regexp suitable for matching an li for a given stack depth
				function regex_for_depth(depth)
				{

					return new RegExp(
						// m[1] = indent, m[2] = list_type
						"(?:^(" + indent_re + "{0," + depth + "} {0,3})(" + any_list + ")\\s+)|" +
						// m[3] = cont
						"(^" + indent_re + "{0," + (depth - 1) + "}[ ]{0,4})"
					);
				}

				function expand_tab(input)
				{
					return input.replace(/ {0,3}\t/g, "    ");
				}

				// Add inline content `inline` to `li`. inline comes from processInline
				// so is an array of content
				function add(li, loose, inline, nl)
				{
					if (loose)
					{
						li.push(["para"].concat(inline));
						return;
					}
					// Hmmm, should this be any block level element or just paras?
					var add_to = li[li.length - 1] instanceof Array && li[li.length - 1][0] == "para"
						? li[li.length - 1]
						: li;

					// If there is already some content in this list, add the new line in
					if (nl && li.length > 1) inline.unshift(nl);

					for (var i = 0; i < inline.length; i++)
					{
						var what = inline[i],
							is_str = typeof what == "string";
						if (is_str && add_to.length > 1 && typeof add_to[add_to.length - 1] == "string")
						{
							add_to[add_to.length - 1] += what;
						}
						else
						{
							add_to.push(what);
						}
					}
				}

				// contained means have an indent greater than the current one. On
				// *every* line in the block
				function get_contained_blocks(depth, blocks)
				{

					var re = new RegExp("^(" + indent_re + "{" + depth + "}.*?\\n?)*$"),
						replace = new RegExp("^" + indent_re + "{" + depth + "}", "gm"),
						ret = [];

					while (blocks.length > 0)
					{
						if (re.exec(blocks[0]))
						{
							var b = blocks.shift(),
								// Now remove that indent
								x = b.replace(replace, "");

							ret.push(mk_block(x, b.trailing, b.lineNumber));
						}
						break;
					}
					return ret;
				}

				// passed to stack.forEach to turn list items up the stack into paras
				function paragraphify(s, i, stack)
				{
					var list = s.list;
					var last_li = list[list.length - 1];

					if (last_li[1] instanceof Array && last_li[1][0] == "para")
					{
						return;
					}
					if (i + 1 == stack.length)
					{
						// Last stack frame
						// Keep the same array, but replace the contents
						last_li.push(["para"].concat(last_li.splice(1)));
					}
					else
					{
						var sublist = last_li.pop();
						last_li.push(["para"].concat(last_li.splice(1)), sublist);
					}
				}

				// The matcher function
				return function (block, next) {
					var m = block.match(is_list_re);
					if (!m) return undefined;

					function make_list(m)
					{
						var list = bullet_list.exec(m[2])
							? ["bulletlist"]
							: ["numberlist"];

						stack.push({list: list, indent: m[1]});
						return list;
					}


					var stack = [], // Stack of lists for nesting.
						list = make_list(m),
						last_li,
						loose = false,
						ret = [stack[0].list],
						i;

					// Loop to search over block looking for inner block elements and loose lists
					loose_search:
						while (true)
						{
							// Split into lines preserving new lines at end of line
							var lines = block.split(/(?=\n)/);

							// We have to grab all lines for a li and call processInline on them
							// once as there are some inline things that can span lines.
							var li_accumulate = "";

							// Loop over the lines in this block looking for tight lists.
							tight_search:
								for (var line_no = 0; line_no < lines.length; line_no++)
								{
									var nl = "",
										l = lines[line_no].replace(/^\n/, function (n) {
											nl = n;
											return "";
										});

									// TODO: really should cache this
									var line_re = regex_for_depth(stack.length);

									m = l.match(line_re);
									//print( "line:", uneval(l), "\nline match:", uneval(m) );

									// We have a list item
									if (m[1] !== undefined)
									{
										// Process the previous list item, if any
										if (li_accumulate.length)
										{
											add(last_li, loose, this.processInline(li_accumulate), nl);
											// Loose mode will have been dealt with. Reset it
											loose = false;
											li_accumulate = "";
										}

										m[1] = expand_tab(m[1]);
										var wanted_depth = Math.floor(m[1].length / 4) + 1;
										//print( "want:", wanted_depth, "stack:", stack.length);
										if (wanted_depth > stack.length)
										{
											// Deep enough for a nested list outright
											//print ( "new nested list" );
											list = make_list(m);
											last_li.push(list);
											last_li = list[1] = ["listitem"];
										}
										else
										{
											// We aren't deep enough to be strictly a new level. This is
											// where Md.pl goes nuts. If the indent matches a level in the
											// stack, put it there, else put it one deeper then the
											// wanted_depth deserves.
											var found = false;
											for (i = 0; i < stack.length; i++)
											{
												if (stack[i].indent != m[1]) continue;
												list = stack[i].list;
												stack.splice(i + 1);
												found = true;
												break;
											}

											if (!found)
											{
												//print("not found. l:", uneval(l));
												wanted_depth++;
												if (wanted_depth <= stack.length)
												{
													stack.splice(wanted_depth);
													//print("Desired depth now", wanted_depth, "stack:", stack.length);
													list = stack[wanted_depth - 1].list;
													//print("list:", uneval(list) );
												}
												else
												{
													//print ("made new stack for messy indent");
													list = make_list(m);
													last_li.push(list);
												}
											}

											//print( uneval(list), "last", list === stack[stack.length-1].list );
											last_li = ["listitem"];
											list.push(last_li);
										} // end depth of shenegains
										nl = "";
									}

									// Add content
									if (l.length > m[0].length)
									{
										li_accumulate += nl + l.substr(m[0].length);
									}
								} // tight_search

							if (li_accumulate.length)
							{
								add(last_li, loose, this.processInline(li_accumulate), nl);
								// Loose mode will have been dealt with. Reset it
								loose = false;
								li_accumulate = "";
							}

							// Look at the next block - we might have a loose list. Or an extra
							// paragraph for the current li
							var contained = get_contained_blocks(stack.length, next);

							// Deal with code blocks or properly nested lists
							if (contained.length > 0)
							{
								// Make sure all listitems up the stack are paragraphs
								forEach(stack, paragraphify, this);

								last_li.push.apply(last_li, this.toTree(contained, []));
							}

							var next_block = next[0] && next[0].valueOf() || "";

							if (next_block.match(is_list_re) || next_block.match(/^ /))
							{
								block = next.shift();

								// Check for an HR following a list: features/lists/hr_abutting
								var hr = this.dialect.block.horizRule(block, next);

								if (hr)
								{
									ret.push.apply(ret, hr);
									break;
								}

								// Make sure all listitems up the stack are paragraphs
								forEach(stack, paragraphify, this);

								loose = true;
								continue loose_search;
							}
							break;
						} // loose_search

					return ret;
				};
			})(),

			blockquote: function blockquote(block, next) {
				if (!block.match(/^>/m))
					return undefined;

				var jsonml = [];

				// separate out the leading abutting block, if any
				if (block[0] != ">")
				{
					var lines = block.split(/\n/),
						prev = [];

					// keep shifting lines until you find a crotchet
					while (lines.length && lines[0][0] != ">")
					{
						prev.push(lines.shift());
					}

					// reassemble!
					block = lines.join("\n");
					jsonml.push.apply(jsonml, this.processBlock(prev.join("\n"), []));
				}

				// if the next block is also a blockquote merge it in
				while (next.length && next[0][0] == ">")
				{
					var b = next.shift();
					block = new String(block + block.trailing + b);
					block.trailing = b.trailing;
				}

				// Strip off the leading "> " and re-process as a block.
				var input = block.replace(/^> ?/gm, ''),
					old_tree = this.tree;
				jsonml.push(this.toTree(input, ["blockquote"]));

				return jsonml;
			},

			referenceDefn: function referenceDefn(block, next) {
				var re = /^\s*\[(.*?)\]:\s*(\S+)(?:\s+(?:(['"])(.*?)\3|\((.*?)\)))?\n?/;
				// interesting matches are [ , ref_id, url, , title, title ]

				if (!block.match(re))
					return undefined;

				// body an attribute node if it doesn't exist
				if (!extract_attr(this.tree))
				{
					this.tree.splice(1, 0, {});
				}

				var attrs = extract_attr(this.tree);

				// body a references hash if it doesn't exist
				if (attrs.references === undefined)
				{
					attrs.references = {};
				}

				var b = this.loop_re_over_block(re, block, function (m) {

					if (m[2] && m[2][0] == '<' && m[2][m[2].length - 1] == '>')
						m[2] = m[2].substring(1, m[2].length - 1);

					var ref = attrs.references[m[1].toLowerCase()] = {
						href: m[2]
					};

					if (m[4] !== undefined)
						ref.title = m[4];
					else if (m[5] !== undefined)
						ref.title = m[5];

				});

				if (b.length)
					next.unshift(mk_block(b, block.trailing));

				return [];
			},

			para: function para(block, next) {
				// everything's a para!
				return [["para"].concat(this.processInline(block))];
			}
		}
	};

	Markdown.dialects.Gruber.inline = {

		__oneElement__: function oneElement(text, patterns_or_re, previous_nodes) {
			var m,
				res,
				lastIndex = 0;

			patterns_or_re = patterns_or_re || this.dialect.inline.__patterns__;
			var re = new RegExp("([\\s\\S]*?)(" + (patterns_or_re.source || patterns_or_re) + ")");

			m = re.exec(text);
			if (!m)
			{
				// Just boring text
				return [text.length, text];
			}
			else if (m[1])
			{
				// Some un-interesting text matched. Return that first
				return [m[1].length, m[1]];
			}

			var res;
			if (m[2] in this.dialect.inline)
			{
				res = this.dialect.inline[m[2]].call(
					this,
					text.substr(m.index), m, previous_nodes || []);
			}
			// Default for now to body dev easier. just slurp special and output it.
			res = res || [m[2].length, m[2]];
			return res;
		},

		__call__: function inline(text, patterns) {

			var out = [],
				res;

			function add(x)
			{
				//D:self.debug("  adding output", uneval(x));
				if (typeof x == "string" && typeof out[out.length - 1] == "string")
					out[out.length - 1] += x;
				else
					out.push(x);
			}

			while (text.length > 0)
			{
				res = this.dialect.inline.__oneElement__.call(this, text, patterns, out);
				text = text.substr(res.shift());
				forEach(res, add)
			}

			return out;
		},

		// These characters are intersting elsewhere, so have rules for them so that
		// chunks of plain text blocks don't include them
		"]": function () {},
		"}": function () {},

		"\\": function escaped(text) {
			// [ length of input processed, node/children to add... ]
			// Only esacape: \ ` * _ { } [ ] ( ) # * + - . !
			if (text.match(/^\\[\\`\*_{}\[\]()#\+.!\-]/))
				return [2, text[1]];
			else
			// Not an esacpe
				return [1, "\\"];
		},

		"![": function image(text) {

			// Unlike images, alt text is plain text only. no other elements are
			// allowed in there

			// ![Alt text](/path/to/img.jpg "Optional title")
			//      1          2            3       4         <--- captures
			var m = text.match(/^!\[(.*?)\][ \t]*\([ \t]*(\S*)(?:[ \t]+(["'])(.*?)\3)?[ \t]*\)/);

			if (m)
			{
				if (m[2] && m[2][0] == '<' && m[2][m[2].length - 1] == '>')
					m[2] = m[2].substring(1, m[2].length - 1);

				m[2] = this.dialect.inline.__call__.call(this, m[2], /\\/)[0];

				var attrs = {alt: m[1], href: m[2] || ""};
				if (m[4] !== undefined)
					attrs.title = m[4];

				return [m[0].length, ["img", attrs]];
			}

			// ![Alt text][id]
			m = text.match(/^!\[(.*?)\][ \t]*\[(.*?)\]/);

			if (m)
			{
				// We can't check if the reference is known here as it likely wont be
				// found till after. Check it in md tree->hmtl tree conversion
				return [m[0].length, ["img_ref", {alt: m[1], ref: m[2].toLowerCase(), original: m[0]}]];
			}

			// Just consume the '!['
			return [2, "!["];
		},

		"[": function link(text) {

			var orig = String(text);
			// Inline content is possible inside `link text`
			var res = Markdown.DialectHelpers.inline_until_char.call(this, text.substr(1), ']');

			// No closing ']' found. Just consume the [
			if (!res) return [1, '['];

			var consumed = 1 + res[0],
				children = res[1],
				link,
				attrs;

			// At this point the first [...] has been parsed. See what follows to find
			// out which kind of link we are (reference or direct url)
			text = text.substr(consumed);

			// [link text](/path/to/img.jpg "Optional title")
			//                 1            2       3         <--- captures
			// This will capture up to the last paren in the block. We then pull
			// back based on if there a matching ones in the url
			//    ([here](/url/(test))
			// The parens have to be balanced
			var m = text.match(/^\s*\([ \t]*(\S+)(?:[ \t]+(["'])(.*?)\2)?[ \t]*\)/);
			if (m)
			{
				var url = m[1];
				consumed += m[0].length;

				if (url && url[0] == '<' && url[url.length - 1] == '>')
					url = url.substring(1, url.length - 1);

				// If there is a title we don't have to worry about parens in the url
				if (!m[3])
				{
					var open_parens = 1; // One open that isn't in the capture
					for (var len = 0; len < url.length; len++)
					{
						switch (url[len])
						{
							case '(':
								open_parens++;
								break;
							case ')':
								if (--open_parens == 0)
								{
									consumed -= url.length - len;
									url = url.substring(0, len);
								}
								break;
						}
					}
				}

				// Process escapes only
				url = this.dialect.inline.__call__.call(this, url, /\\/)[0];

				attrs = {href: url || ""};
				if (m[3] !== undefined)
					attrs.title = m[3];

				link = ["link", attrs].concat(children);
				return [consumed, link];
			}

			// [Alt text][id]
			// [Alt text] [id]
			m = text.match(/^\s*\[(.*?)\]/);

			if (m)
			{

				consumed += m[0].length;

				// [links][] uses links as its reference
				attrs = {ref: (m[1] || String(children)).toLowerCase(), original: orig.substr(0, consumed)};

				link = ["link_ref", attrs].concat(children);

				// We can't check if the reference is known here as it likely wont be
				// found till after. Check it in md tree->hmtl tree conversion.
				// Store the original so that conversion can revert if the ref isn't found.
				return [consumed, link];
			}

			// [id]
			// Only if id is plain (no formatting.)
			if (children.length == 1 && typeof children[0] == "string")
			{

				attrs = {ref: children[0].toLowerCase(), original: orig.substr(0, consumed)};
				link = ["link_ref", attrs, children[0]];
				return [consumed, link];
			}

			// Just consume the '['
			return [1, "["];
		},


		"<": function autoLink(text) {
			var m;

			if ((m = text.match(/^<(?:((https?|ftp|mailto):[^>]+)|(.*?@.*?\.[a-zA-Z]+))>/)) != null)
			{
				if (m[3])
				{
					return [m[0].length, ["link", {href: "mailto:" + m[3]}, m[3]]];

				}
				else if (m[2] == "mailto")
				{
					return [m[0].length, ["link", {href: m[1]}, m[1].substr("mailto:".length)]];
				}
				else
					return [m[0].length, ["link", {href: m[1]}, m[1]]];
			}

			return [1, "<"];
		},

		"`": function inlineCode(text) {
			// Inline code block. as many backticks as you like to start it
			// Always skip over the opening ticks.
			var m = text.match(/(`+)(([\s\S]*?)\1)/);

			if (m && m[2])
				return [m[1].length + m[2].length, ["inlinecode", m[3]]];
			else
			{
				// TODO: No matching end code found - warn!
				return [1, "`"];
			}
		},

		"  \n": function lineBreak(text) {
			return [3, ["linebreak"]];
		}

	};

// Meta Helper/generator method for em and strong handling
	function strong_em(tag, md)
	{

		var state_slot = tag + "_state",
			other_slot = tag == "strong" ? "em_state" : "strong_state";

		function CloseTag(len)
		{
			this.len_after = len;
			this.name = "close_" + md;
		}

		return function (text, orig_match) {

			if (this[state_slot][0] == md)
			{
				// Most recent em is of this type
				//D:this.debug("closing", md);
				this[state_slot].shift();

				// "Consume" everything to go back to the recrusion in the else-block below
				return [text.length, new CloseTag(text.length - md.length)];
			}
			else
			{
				// Store a clone of the em/strong states
				var other = this[other_slot].slice(),
					state = this[state_slot].slice();

				this[state_slot].unshift(md);

				//D:this.debug_indent += "  ";

				// Recurse
				var res = this.processInline(text.substr(md.length));
				//D:this.debug_indent = this.debug_indent.substr(2);

				var last = res[res.length - 1];

				//D:this.debug("processInline from", tag + ": ", uneval( res ) );

				var check = this[state_slot].shift();
				if (last instanceof CloseTag)
				{
					res.pop();
					// We matched! Huzzah.
					var consumed = text.length - last.len_after;
					return [consumed, [tag].concat(res)];
				}
				else
				{
					// Restore the state of the other kind. We might have mistakenly closed it.
					this[other_slot] = other;
					this[state_slot] = state;

					// We can't reuse the processed result as it could have wrong parsing contexts in it.
					return [md.length, md];
				}
			}
		}; // End returned function
	}

	Markdown.dialects.Gruber.inline["**"] = strong_em("strong", "**");
	Markdown.dialects.Gruber.inline["__"] = strong_em("strong", "__");
	Markdown.dialects.Gruber.inline["*"] = strong_em("em", "*");
	Markdown.dialects.Gruber.inline["_"] = strong_em("em", "_");


// Build default order from insertion order.
	Markdown.buildBlockOrder = function (d) {
		var ord = [];
		for (var i in d)
		{
			if (i == "__order__" || i == "__call__") continue;
			ord.push(i);
		}
		d.__order__ = ord;
	};

// Build patterns for inline matcher
	Markdown.buildInlinePatterns = function (d) {
		var patterns = [];

		for (var i in d)
		{
			// __foo__ is reserved and not a pattern
			if (i.match(/^__.*__$/)) continue;
			var l = i.replace(/([\\.*+?|()\[\]{}])/g, "\\$1").replace(/\n/, "\\n");
			patterns.push(i.length == 1 ? l : "(?:" + l + ")");
		}

		patterns = patterns.join("|");
		d.__patterns__ = patterns;
		//print("patterns:", uneval( patterns ) );

		var fn = d.__call__;
		d.__call__ = function (text, pattern) {
			if (pattern != undefined)
			{
				return fn.call(this, text, pattern);
			}
			else
			{
				return fn.call(this, text, patterns);
			}
		};
	};

	Markdown.DialectHelpers = {};
	Markdown.DialectHelpers.inline_until_char = function (text, want) {
		var consumed = 0,
			nodes = [];

		while (true)
		{
			if (text[consumed] == want)
			{
				// Found the character we were looking for
				consumed++;
				return [consumed, nodes];
			}

			if (consumed >= text.length)
			{
				// No closing char found. Abort.
				return null;
			}

			var res = this.dialect.inline.__oneElement__.call(this, text.substr(consumed));
			consumed += res[0];
			// Add any returned nodes.
			nodes.push.apply(nodes, res.slice(1));
		}
	}

// Helper function to body sub-classing a dialect easier
	Markdown.subclassDialect = function (d) {
		function Block() {}

		Block.prototype = d.block;

		function Inline() {}

		Inline.prototype = d.inline;

		return {block: new Block(), inline: new Inline()};
	};

	Markdown.buildBlockOrder(Markdown.dialects.Gruber.block);
	Markdown.buildInlinePatterns(Markdown.dialects.Gruber.inline);

	Markdown.dialects.Maruku = Markdown.subclassDialect(Markdown.dialects.Gruber);

	Markdown.dialects.Maruku.processMetaHash = function processMetaHash(meta_string) {
		var meta = split_meta_hash(meta_string),
			attr = {};

		for (var i = 0; i < meta.length; ++i)
		{
			// id: #foo
			if (/^#/.test(meta[i]))
			{
				attr.id = meta[i].substring(1);
			}
			// class: .foo
			else if (/^\./.test(meta[i]))
			{
				// if class already exists, append the new one
				if (attr['class'])
				{
					attr['class'] = attr['class'] + meta[i].replace(/./, " ");
				}
				else
				{
					attr['class'] = meta[i].substring(1);
				}
			}
			// attribute: foo=bar
			else if (/\=/.test(meta[i]))
			{
				var s = meta[i].split(/\=/);
				attr[s[0]] = s[1];
			}
		}

		return attr;
	}

	function split_meta_hash(meta_string)
	{
		var meta = meta_string.split(""),
			parts = [""],
			in_quotes = false;

		while (meta.length)
		{
			var letter = meta.shift();
			switch (letter)
			{
				case " " :
					// if we're in a quoted section, keep it
					if (in_quotes)
					{
						parts[parts.length - 1] += letter;
					}
					// otherwise body a new part
					else
					{
						parts.push("");
					}
					break;
				case "'" :
				case '"' :
					// reverse the quotes and move straight on
					in_quotes = !in_quotes;
					break;
				case "\\" :
					// shift off the next letter to be used straight away.
					// it was escaped so we'll keep it whatever it is
					letter = meta.shift();
				default :
					parts[parts.length - 1] += letter;
					break;
			}
		}

		return parts;
	}

	Markdown.dialects.Maruku.block.document_meta = function document_meta(block, next) {
		// we're only interested in the first block
		if (block.lineNumber > 1) return undefined;

		// document_meta blocks consist of one or more lines of `Key: Value\n`
		if (!block.match(/^(?:\w+:.*\n)*\w+:.*$/)) return undefined;

		// body an attribute node if it doesn't exist
		if (!extract_attr(this.tree))
		{
			this.tree.splice(1, 0, {});
		}

		var pairs = block.split(/\n/);
		for (p in pairs)
		{
			var m = pairs[p].match(/(\w+):\s*(.*)$/),
				key = m[1].toLowerCase(),
				value = m[2];

			this.tree[1][key] = value;
		}

		// document_meta produces no content!
		return [];
	};

	Markdown.dialects.Maruku.block.block_meta = function block_meta(block, next) {
		// check if the last line of the block is an meta hash
		var m = block.match(/(^|\n) {0,3}\{:\s*((?:\\\}|[^\}])*)\s*\}$/);
		if (!m) return undefined;

		// process the meta hash
		var attr = this.dialect.processMetaHash(m[2]);

		var hash;

		// if we matched ^ then we need to apply meta to the previous block
		if (m[1] === "")
		{
			var node = this.tree[this.tree.length - 1];
			hash = extract_attr(node);

			// if the node is a string (rather than JsonML), bail
			if (typeof node === "string") return undefined;

			// create the attribute hash if it doesn't exist
			if (!hash)
			{
				hash = {};
				node.splice(1, 0, hash);
			}

			// add the attributes in
			for (a in attr)
			{
				hash[a] = attr[a];
			}

			// return nothing so the meta hash is removed
			return [];
		}

		// pull the meta hash off the block and process what's left
		var b = block.replace(/\n.*$/, ""),
			result = this.processBlock(b, []);

		// get or body the attributes hash
		hash = extract_attr(result[0]);
		if (!hash)
		{
			hash = {};
			result[0].splice(1, 0, hash);
		}

		// attach the attributes to the block
		for (a in attr)
		{
			hash[a] = attr[a];
		}

		return result;
	};

	Markdown.dialects.Maruku.block.definition_list = function definition_list(block, next) {
		// one or more terms followed by one or more definitions, in a single block
		var tight = /^((?:[^\s:].*\n)+):\s+([\s\S]+)$/,
			list = ["dl"],
			i;

		// see if we're dealing with a tight or loose block
		if ((m = block.match(tight)))
		{
			// pull subsequent tight DL blocks out of `next`
			var blocks = [block];
			while (next.length && tight.exec(next[0]))
			{
				blocks.push(next.shift());
			}

			for (var b = 0; b < blocks.length; ++b)
			{
				var m = blocks[b].match(tight),
					terms = m[1].replace(/\n$/, "").split(/\n/),
					defns = m[2].split(/\n:\s+/);

				// print( uneval( m ) );

				for (i = 0; i < terms.length; ++i)
				{
					list.push(["dt", terms[i]]);
				}

				for (i = 0; i < defns.length; ++i)
				{
					// run inline processing over the definition
					list.push(["dd"].concat(this.processInline(defns[i].replace(/(\n)\s+/, "$1"))));
				}
			}
		}
		else
		{
			return undefined;
		}

		return [list];
	};

	Markdown.dialects.Maruku.inline["{:"] = function inline_meta(text, matches, out) {
		if (!out.length)
		{
			return [2, "{:"];
		}

		// get the preceeding element
		var before = out[out.length - 1];

		if (typeof before === "string")
		{
			return [2, "{:"];
		}

		// match a meta hash
		var m = text.match(/^\{:\s*((?:\\\}|[^\}])*)\s*\}/);

		// no match, false alarm
		if (!m)
		{
			return [2, "{:"];
		}

		// attach the attributes to the preceeding element
		var meta = this.dialect.processMetaHash(m[1]),
			attr = extract_attr(before);

		if (!attr)
		{
			attr = {};
			before.splice(1, 0, attr);
		}

		for (var k in meta)
		{
			attr[k] = meta[k];
		}

		// cut out the string and replace it with nothing
		return [m[0].length, ""];
	};

	Markdown.buildBlockOrder(Markdown.dialects.Maruku.block);
	Markdown.buildInlinePatterns(Markdown.dialects.Maruku.inline);

	var isArray = Array.isArray || function (obj) {
		return Object.prototype.toString.call(obj) == '[object Array]';
	};

	var forEach;
// Don't mess with Array.prototype. Its not friendly
	if (Array.prototype.forEach)
	{
		forEach = function (arr, cb, thisp) {
			return arr.forEach(cb, thisp);
		};
	}
	else
	{
		forEach = function (arr, cb, thisp) {
			for (var i = 0; i < arr.length; i++)
			{
				cb.call(thisp || arr, arr[i], i, arr);
			}
		}
	}

	function extract_attr(jsonml)
	{
		return isArray(jsonml)
		&& jsonml.length > 1
		&& typeof jsonml[1] === "object"
		&& !(isArray(jsonml[1]))
			? jsonml[1]
			: undefined;
	}


	/**
	 *  renderJsonML( jsonml[, options] ) -> String
	 *  - jsonml (Array): JsonML array to render to XML
	 *  - options (Object): options
	 *
	 *  Converts the given JsonML into well-formed XML.
	 *
	 *  The options currently understood are:
	 *
	 *  - root (Boolean): wether or not the root node should be included in the
	 *    output, or just its children. The default `false` is to not include the
	 *    root itself.
	 */
	expose.renderJsonML = function (jsonml, options) {
		options = options || {};
		// include the root element in the rendered output?
		options.root = options.root || false;

		var content = [];

		if (options.root)
		{
			content.push(render_tree(jsonml));
		}
		else
		{
			jsonml.shift(); // get rid of the tag
			if (jsonml.length && typeof jsonml[0] === "object" && !(jsonml[0] instanceof Array))
			{
				jsonml.shift(); // get rid of the attributes
			}

			while (jsonml.length)
			{
				content.push(render_tree(jsonml.shift()));
			}
		}

		return content.join("\n\n");
	};

	function escapeHTML(text)
	{
		return text.replace(/&/g, "&amp;").replace(/</g, "&lt;").replace(/>/g, "&gt;").replace(/"/g, "&quot;").replace(/'/g, "&#39;");
	}

	function render_tree(jsonml)
	{
		// basic case
		if (typeof jsonml === "string")
		{
			return escapeHTML(jsonml);
		}

		var tag = jsonml.shift(),
			attributes = {},
			content = [];

		if (jsonml.length && typeof jsonml[0] === "object" && !(jsonml[0] instanceof Array))
		{
			attributes = jsonml.shift();
		}

		while (jsonml.length)
		{
			content.push(arguments.callee(jsonml.shift()));
		}

		var tag_attrs = "";
		for (var a in attributes)
		{
			tag_attrs += " " + a + '="' + escapeHTML(attributes[a]) + '"';
		}

		// be careful about adding whitespace here for inline elements
		if (tag == "img" || tag == "br" || tag == "hr")
		{
			return "<" + tag + tag_attrs + "/>";
		}
		else
		{
			return "<" + tag + tag_attrs + ">" + content.join("") + "</" + tag + ">";
		}
	}

	function convert_tree_to_html(tree, references, options)
	{
		var i;
		options = options || {};

		// shallow clone
		var jsonml = tree.slice(0);

		if (typeof options.preprocessTreeNode === "function")
		{
			jsonml = options.preprocessTreeNode(jsonml, references);
		}

		// Clone attributes if they exist
		var attrs = extract_attr(jsonml);
		if (attrs)
		{
			jsonml[1] = {};
			for (i in attrs)
			{
				jsonml[1][i] = attrs[i];
			}
			attrs = jsonml[1];
		}

		// basic case
		if (typeof jsonml === "string")
		{
			return jsonml;
		}

		// convert this node
		switch (jsonml[0])
		{
			case "header":
				jsonml[0] = "h" + jsonml[1].level;
				delete jsonml[1].level;
				break;
			case "bulletlist":
				jsonml[0] = "ul";
				break;
			case "numberlist":
				jsonml[0] = "ol";
				break;
			case "listitem":
				jsonml[0] = "li";
				break;
			case "para":
				jsonml[0] = "p";
				break;
			case "markdown":
				jsonml[0] = "html";
				if (attrs) delete attrs.references;
				break;
			case "code_block":
				jsonml[0] = "pre";
				i = attrs ? 2 : 1;
				var code = ["code"];
				code.push.apply(code, jsonml.splice(i));
				jsonml[i] = code;
				break;
			case "inlinecode":
				jsonml[0] = "code";
				break;
			case "img":
				jsonml[1].src = jsonml[1].href;
				delete jsonml[1].href;
				break;
			case "linebreak":
				jsonml[0] = "br";
				break;
			case "link":
				jsonml[0] = "a";
				break;
			case "link_ref":
				jsonml[0] = "a";

				// grab this ref and clean up the attribute node
				var ref = references[attrs.ref];

				// if the reference exists, body the link
				if (ref)
				{
					delete attrs.ref;

					// add in the href and title, if present
					attrs.href = ref.href;
					if (ref.title)
					{
						attrs.title = ref.title;
					}

					// get rid of the unneeded original text
					delete attrs.original;
				}
				// the reference doesn't exist, so revert to plain text
				else
				{
					return attrs.original;
				}
				break;
			case "img_ref":
				jsonml[0] = "img";

				// grab this ref and clean up the attribute node
				var ref = references[attrs.ref];

				// if the reference exists, body the link
				if (ref)
				{
					delete attrs.ref;

					// add in the href and title, if present
					attrs.src = ref.href;
					if (ref.title)
					{
						attrs.title = ref.title;
					}

					// get rid of the unneeded original text
					delete attrs.original;
				}
				// the reference doesn't exist, so revert to plain text
				else
				{
					return attrs.original;
				}
				break;
		}

		// convert all the children
		i = 1;

		// deal with the attribute node, if it exists
		if (attrs)
		{
			// if there are keys, skip over it
			for (var key in jsonml[1])
			{
				i = 2;
			}
			// if there aren't, remove it
			if (i === 1)
			{
				jsonml.splice(i, 1);
			}
		}

		for (; i < jsonml.length; ++i)
		{
			jsonml[i] = arguments.callee(jsonml[i], references, options);
		}

		return jsonml;
	}


// merges adjacent text nodes into a single node
	function merge_text_nodes(jsonml)
	{
		// skip the tag name and attribute hash
		var i = extract_attr(jsonml) ? 2 : 1;

		while (i < jsonml.length)
		{
			// if it's a string check the next item too
			if (typeof jsonml[i] === "string")
			{
				if (i + 1 < jsonml.length && typeof jsonml[i + 1] === "string")
				{
					// merge the second string into the first and remove it
					jsonml[i] += jsonml.splice(i + 1, 1)[0];
				}
				else
				{
					++i;
				}
			}
			// if it's not a string recurse
			else
			{
				arguments.callee(jsonml[i]);
				++i;
			}
		}
	}

})((function () {
	if (typeof exports === "undefined")
	{
		window.markdown = {};
		return window.markdown;
	}
	else
	{
		return exports;
	}
})());
